package com.lw.leetcode.arr.c;

/**
 * 1074. 元素和为目标值的子矩阵数量
 *
 * @Author liw
 * @Date 2021/5/29 16:57
 * @Version 1.0
 */
public class NumSubmatrixSumTarget {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int a = matrix.length;
        int b = matrix[0].length;
        int[][] arr = new int[a + 1][b + 1];
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                arr[i + 1][j + 1] = arr[i + 1][j] + arr[i][j + 1] - arr[i][j] + matrix[i][j];
            }
        }
        int result = 0;
        for (int i = 1; i <= a; i++) {
            for (int j = 1; j <= b; j++) {
                for (int k = i; k <= a; k++) {
                    for (int n = j; n <= b; n++) {
                        if (arr[k][n] - arr[i - 1][n] - arr[k][j - 1] + arr[i - 1][j - 1] == target) {
                            result++;
                        }
                    }
                }
            }
        }
        return result;
    }
}
